package a03_哈希;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <p>
 * a09_四数之和复习5
 * </p>
 *
 * @author flyduck
 * @since 2025/2/19
 */
public class a09_四数之和复习5 {

    public static void main(String[] args) {
        a09_四数之和复习5 test = new a09_四数之和复习5();
        System.out.println(test.fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0));
    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> resultList = new ArrayList<>();

        Arrays.sort(nums);
        //-2 -1 0 0 1 2
        outer1:for (int i = 0; i < nums.length; i++) {
            if(nums[i] > 0 && target > 0 && nums[i] > target){
                break outer1;
            }
            if(i > 0 && nums[i] == nums[i-1]){
                continue outer1;
            }
            outer2:for (int j = i + 1; j < nums.length; j++) {
                if(nums[i] + nums[j] > 0 && target > 0 && nums[i] + nums[j] > target){
                    break outer2;
                }
                if(j > i+1 && nums[j] == nums[j-1]){
                    continue outer2;
                }

                int m = j+1;
                int n = nums.length - 1;
                inner:while (m < n){
                    if(m > j+1 && nums[m] == nums[m-1]){
                        m++;
                        continue inner;
                    }
                    if(n < nums.length - 1 && nums[n] == nums[n+1]){
                        n--;
                        continue inner;
                    }

                    long sum = (long)nums[i] + nums[j] + nums[m] + nums[n];
                    if(sum < target){
                        m++;
                    }else if(sum > target){
                        n--;
                    }else {
                        List<Integer> result = new ArrayList<>();
                        result.add(nums[i]);
                        result.add(nums[j]);
                        result.add(nums[m]);
                        result.add(nums[n]);
                        resultList.add(result);
                        m++;
                        n--;
                    }
                }
            }
        }
        return resultList;
    }
}
